﻿// 602 [CF 1385D] a-Good String.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;
/*
http://oj.daimayuan.top/course/22/problem/978

给你一个长度为 n的由小写字母组成的字符串 s，保证 n=2k，其中 k为大于等于零的整数。

一个非空字符串 s被称为 c-good（c为 a...z中的某个字母）的，需要满足下列三个条件之一：

s长度为 1
，且只含有 c字符；
s长度大于 1
，且 s的前一半全为字符 c
，后一半为 next(c)-good的字符串，其中 next(c)表示 c后面的那一个字母；
 s长度大于 1，且 s的前一半为 next(c)-good的字符串，后一半全为字符 c；

例如 aabc 是 a-good的，ffgheeee 是 e-good的。

对于给定的字符串 s，请求出最少改变 s中几个字符可以把它变成 a-good的字符串。

输入格式
输入有多组询问。

第一行一个整数 T
 表示数据组数。

对于每组数据包含两行，第一行一个整数 n
，第二行一个长度为 n的字符串 s。

输出格式
对于每组数据，输出一行一个整数表示答案。

样例输入
5
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z



1
8
ffgheeee

样例输出
0
7
4
5
1
数据规模
对于 100%的数据，保证 1≤T≤5,1≤n≤131072
，保证 n=2k，其中 k为大于等于零的整数。
*/

int test, n;
char s[200001];

int solve(int l, int r, int x) {
	if (l == r) {
		if (x == s[l])
			return 0;
		else
			return 1;
	}
	int m = (l + r) / 2;
	int y1 = 0, y2 = 0;
	for (int i = l; i <= m; i++) {
		if (s[i] != x)
			++y1;
	}
	for (int i = m + 1; i <= r; i++) {
		if (s[i] != x)
			++y2;
	}

	int a = y1 + solve(m + 1, r, x + 1);
	int b = y2 + solve(l, m, x + 1);

	return min(a,b);
}

int main()
{
	scanf("%d", &test);
	for (; test--;) {
		scanf("%d%s", &n, s + 1);
		printf("%d\n",solve(1,n,'a'));
	}

	return 0;
}

 